#define _CRT_SECURE_NO_WARNINGS
//#include<iostream>
//using namespace std;
//const int N = 1e4 + 10;
//int a[N][5];
//int main()
//{
//	int n; cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4];
//	}
//	int x, y; cin >> x >> y;
//	for (int i = n; i >= 1; i--)
//	{
//		if (x >= a[i][1] && x <= a[i][1] + a[1][3] && y <= a[i][2] + a[i][4] && y >= a[i][2])
//		{
//			cout << i << endl;
//			return 0;
//		}
//	}
//	cout << -1 << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//int a[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
//int main()
//{
//	int x, y;
//	cin >> x >> y;
//	int cnt=0;
//	for (int i = 1; i <= 12; i++)
//	{
//		for (int j = 1; j <= a[i]; j++)
//		{
//			int tmp = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;
//			int ret = tmp * 10000 + i * 100 + j;
//			if (ret >= x && ret <= y) cnt++;
//		}
//	}
//	cout << cnt << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e4 + 10;
//int a[N][3];
//int main()
//{
//	int n,cnt=0; cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i][2];
//	for (int i = 0; i <= 1; i++)
//	{
//		int flag = 0;
//		a[1][1] = i;
//		for (int j = 1; j <= n; j++)
//		{
//			a[j + 1][1] = a[j][2] - a[j][1] - a[j - 1][1];
//			int x = a[j + 1][1];
//			if (x < 0 || x>1) {
//				flag = 1;
//				break;
//			}
//		}
//		if (a[n + 1][1] == 0 && flag == 0) cnt++;
//	}
//	cout << cnt << endl;
//	return 0;
//}
//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N=10;
//int a[N], t[N];
//int cal(int x)
//{
//	int cnt = 0;
//	while (x)
//	{
//		cnt++;
//		x &= (x - 1);
//	}
//	return cnt;
//}
//int main()
//{
//	int m; cin >> m;
//	while (m--)
//	{
//		memset(a, 0, sizeof a);
//		for (int i = 0; i < 5; i++)
//		{
//			for (int j = 0; j < 5; j++)
//			{
//				char x; cin >> x;
//				if (x == '0') a[i] |= 1 << j;
//			}
//		}
//		int ret = 0x3f3f3f3f;
//		for (int st = 0; st < (1 << 5); st++)
//		{
//			memcpy(t, a, sizeof a);
//			int push = st;
//			int cnt = 0;
//			for (int i = 0; i < 5; i++)
//			{
//				cnt += cal(push);
//				t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);
//				t[i] &= (1 << 5) - 1;
//				t[i + 1] = t[i + 1] ^ push;
//				push = t[i];
//			}
//			if (t[4] == 0) ret = min(ret, cnt);
//		}
//		if (ret <= 6) cout << ret << endl;
//		else cout << -1 << endl;
//	}
//	return 0;
//}
//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 20;
//int a[N], t[N];
//int n;
//int sum(int x, int y)
//{
//	int cnt = 0;
//	for (int i = 0; i < n; i++)
//	{
//		if (((x >> i)&1) == 0 && ((y >> i)&1) == 1) cnt++;
//		if (((x >> i) & 1) == 1 && ((y >> i) & 1) == 0) return -1;
//	}
//	return cnt;
//}
//int cal()
//{
//	int ret = 0x3f3f3f3f;
//	for (int st = 0; st < (1<<n); st++)
//	{
//		memcpy(t, a, sizeof a);
//		int change = st, cnt = 0, flag = 0;
//		for (int i = 1; i <= n; i++)
//		{
//			int c = sum(t[i], change);
//			if (c == -1)
//			{
//				flag = 1;
//				break;
//			}
//			cnt += c;
//			t[i] = change;
//			change = t[i - 1] ^ (t[i] << 1) ^ (t[i] >> 1);
//			change &= (1 << n) - 1;
//		}
//		if (flag == 0) ret=min(ret,cnt);
//	}
//	if (ret == 0x3f3f3f3f) return -1;
//	else return ret;
//}
//int main()
//{
//	int T; cin >> T;
//	for(int k=1;k<=T;k++)
//	{
//		cin >> n;
//		memset(a, 0, sizeof a);
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 0; j < n; j++)
//			{
//				int x; cin >> x;
//				if(x) a[i] |= (x<<j);
//			}
//		}
//		printf("Case %d: %d\n", k, cal());
//	}
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//long long a[N], f[N];
//int main()
//{
//    int n, m; cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        int x; cin >> x;
//        f[i] = f[i - 1] + x;
//    }
//    while (m--)
//    {
//        int l, r; cin >> l >> r;
//        cout << f[r] - f[l - 1] << endl;
//    }
//    return 0;
//}
//#include<iostream>
//using namespace std;
//const int  N = 2e5 + 10;
//long long f[N];
//long long m;
//int main()
//{
//	int n; cin >> n;
//	long long ret = -1e20;
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		f[i] = f[i - 1] + x;
//		ret = max(ret, f[i] - m);
//		m = min(m, f[i]);
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e3 + 10;
//typedef long long LL;
//LL f[N][N];
//int main()
//{
//    int n, m, q; cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            int x; cin >> x;
//            f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + x;
//        }
//    }
//    while (q--)
//    {
//        int a, b, x, y;
//        cin >> a >> b >> x >> y;
//        cout << f[x][y] + f[a - 1][b - 1] - f[a - 1][y] - f[x][b - 1] << endl;
//    }
//    return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 5e3 + 10;
//int a[N][N], f[N][N];
//int main()
//{
//	int n, m; cin >> n >> m;
//	while (n--)
//	{
//		int x, y, v;
//		cin >> x>> y >> v;
//		a[++x][++y] += v;
//	}
//	n = 5001;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= n;j++)
//		{
//			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i-1][j-1] + a[i][j];
//		}
//	}
//	int ret = 0;
//	m = min(m, n);
//	for (int i = m; i <= n; i++)
//	{
//		for (int j = m; j <= n; j++)
//		{
//			int x = i - m + 1, y = j - m + 1;
//			ret = max(ret, f[i][j] + f[x - 1][y - 1] - f[x - 1][j] - f[i][y - 1]);
//		}
//	}
//	cout << ret;
//	return 0;
//}